package leetcode.weekly.week311;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import leetcode.helper.tree.TreeNode;

//Solution3Test
public class Solution3 {

	public TreeNode reverseOddLevels(TreeNode root) {
		List<TreeNode> o = new ArrayList<>();
		o.add(root);
		while (o != null && o.size() != 0) {
			List<TreeNode> no = new ArrayList<>();
			List<TreeNode> myj = new ArrayList<>();
			if (o.get(0) == null || o.get(0).left == null) {
				break;
			}
			for (int i = 0; i < o.size(); i++) {
				myj.add(o.get(i).left);
				myj.add(o.get(i).right);
				if (o.get(i).left != null) {
					no.add(o.get(i).left.left);
					no.add(o.get(i).left.right);
					no.add(o.get(i).right.left);
					no.add(o.get(i).right.right);
				}
			}
			int p = myj.size();
			for (int i = 0; i < o.size(); i++) {
				o.get(i).left = myj.get(--p);
				o.get(i).right = myj.get(--p);
			}
			p = 0;
			if (no.get(0) != null)
				for (int i = 0; i < o.size(); i++) {
					o.get(i).left.left = no.get(p++);
					o.get(i).left.right = no.get(p++);
					o.get(i).right.left = no.get(p++);
					o.get(i).right.right = no.get(p++);
				}
			o = no;
		}
		return root;
	}
}
